//Priority queue based on array

#ifndef APQUEUE_H
#define APQUEUE_H

#include "RuntimeException.h"
#include "Item.h"
#include <algorithm> //may not be needed
#include <vector>

template <typename T>
class APQueue {
protected:
	typedef Item<T> I;
	typedef PQComp<T> P;
private:
	std::vector<I> Y;
	static const int DEF_SIZE = 8;
	static const int U_INT_MAX = 65535;
	//int cmps;
public:

	struct EmptyPriorityQueue : public RuntimeException {
		EmptyPriorityQueue() : RuntimeException("Queue is Empty") {}
	};

	APQueue(int size = 0) : Y(size) {} //size used to be DEF_SIZE
	bool empty() const { return Y.empty(); }
	int* insert_item(const unsigned int k, const T& e, int& num_cmps) {
		int* pos = new int[1];
		*pos = Y.size();
		Y.push_back(I(k,e,pos)); //Allowed since this is unsorted
		//I temp(k,e,pos);
		//update_key(pos,k,num_cmps);
		return pos;
	}
	
	const T& min_elem() throw(EmptyPriorityQueue){
		if (Y.empty()) throw EmptyPriorityQueue();

		int index = 0;
		int min = Y[index].get_key();

		for (int i = 1; i < Y.size(); i++)
		{
			if (Y[i].get_key() < Y[index].get_key())
				index = i;
		}
		return Y[index].get_elem();
		
		/*I *temp;
		unsigned int min = U_INT_MAX;
		for (int i = 0; i < Y.size(); i++)
		{
			if (Y[i].get_key() < min){
				min = Y[i].get_key();
				temp = &Y[i];
			}
		}
		return temp->get_elem();*/
	}
	
	const int min_key() throw(EmptyPriorityQueue) { //There may exist a more efficient way of doing this
		if (Y.empty()) throw EmptyPriorityQueue();

		int index = 0;
		int min = Y[index].get_key();

		for (int i = 1; i < Y.size(); i++)
		{
			if (Y[i].get_key() < Y[index].get_key())
				index = i;
		}
		return Y[index].get_key();
		
		/*I *temp;
		unsigned int min = U_INT_MAX;
		for (int i = 0; i < Y.size(); i++)
		{
			if (Y[i].get_key() < min)
			{
				min = Y[i].get_key();
				temp = &Y[i];
			}
		}
		return temp->get_key();*/
	}
	
	void remove_min(int& num_cmps) throw(EmptyPriorityQueue) {
		if (Y.empty()) throw EmptyPriorityQueue();
		int j=0;
		unsigned int min = U_INT_MAX;
		for (int i = 0; i < Y.size(); i++)
		{
			if (Y[i].get_key() < min){
				min = Y[i].get_key(); //update min
				j = i; //record position
			}
			num_cmps++;
		}
		Y.erase(Y.begin()+j);
		//update positions
		for (int i = j; i < Y.size(); i++)
		{
			*Y[i].pos = i;
		}
	}
	
	void update_key(int* pos, unsigned int k, int& num_cmps) {
		//int end = Y.size()-1;
		Y[*pos].set_key(k);
		
		/*int conf_p = 0;
		int conf_k = k;
		
		for (int i = conf_p; i < Y.size()-1; i++)
		{
			num_cmps++;
			if (conf_k == Y[i].get_key()) //conflict found
			{
				conf_k++;
				Y[i].set_key(conf_k);
			}
			*(Y[i].pos) = i; //update position
		}*/
		/*last.set_key(k);
		*(last.pos) = end; //update position of last element*/
	}
	
	int size()
	{
		return Y.size();
	}
	void print()
	{
		if (Y.empty()){
			std::cout << "Queue is empty. Moving on.\n";
		}
		for (int i = 0; i < Y.size(); i++)
		{
			std::cout << "Element: " << Y[i].get_elem()
				<< "; Key: " << Y[i].get_key() << '\n';
		}
	}
};

#endif
